There are a great many instances in which it is important to monitor or manipulate data at the time an event is occurring, or to coordinate data that will be used in the future, for example editing audio/video material for future playback.
If an industrial process is running out of control, and, for example, about to overheat and spoil a batch of compound, or if an autopilot in an airplane or many other industrial processes are to be monitored and controlled effectively, it is important that these events be managed in real time, or as close as possible to the actual time of the events of significance.
If a security system is to report the activities of individuals at certain times, it is important to know that some undesirable event is taking place on the loading dock right when it is happening, not some time later.
In making a movie, it is important that the sound and the action be closely synchronized, and that the time for playback is consistent each time.
From a more detailed perspective, within the operation of a computer, it is important that certain information be collected in a timely manner. For example, certain information (a) will be presented once and only once and if missed can never be recovered, or (b) will be presented again and again, as needed, until correctly received but if improperly received will be sent again, thus imposing a time penalty by slowing down transmission of additional information.
In these and in many more instances, it is important to consider the effect of time on the coordination of various events. In particular, many events are best monitored in "real time", and in the ideal this means at the actual time of the actual event (within a small time threshold, preferably on the order of milliseconds or, for some tasks, much much less).
What is "Real Time"? Real time is used in many separate but related senses; each has relevance for defining real time requirements. "Real time" is used:
1. as a synonym for `low latency`, especially with reference to e.g. games in which the fastest possible response by the game to user input from a game controller is required PA1 2. referring to equivalence of elapsed time, as when a recording medium accepts a signal representing a live event and the recording consumes exactly the amount of time the live event did PA1 3. referring to streaming data delivery systems in which the specific order of data (in time) and the rate(s) at which they are delivered are their salient properties PA1 4. to designate hard real time implementations, meaning systems in which a computed result (often a decision to take an action) absolutely must be completed by no later than a stipulated deadline; common in avionics, weaponry, medical and other "mission critical" applications, among others PA1 5. in the sense of clock time, referring to the absolute time expressed in some conventional unit, as in "4:30 PM", or to a range of such times PA1 6. for process control applications, in which the structure, dynamics, and coordination of processes must proceed (often adaptively) according to strict timing and scheduling criteria; often arising in e.g. manufacturing applications, in which motion and amplitudes must be computed to conform to trajectories or models, and often incorporating closed loop feedback and control
Variously these differing senses are sometimes referred to as "hard" or "soft" real time. These senses have in common the fact that they differ completely from the prevalent conventional model of computation, in which the only temporal criterion is minimization of execution time, as opposed to fulfillment of schedules and guarantees of timely execution and quality of service.
There are a number of "real time" operating systems currently available. There include products such as Wind River, Lynx, Ready, RT Mach, OS/9 (Microware), RTEMS, with many more being researched and discussed in the engineering literature.
In the normal operation of a computer, each process for the central processor must be scheduled and coordinated with other processes. Prioritizing and scheduling tasks is an important function of the operating system, and significantly related to the architecture of the computer system. The scheduler needs to allocate execution priorities. Most of these are deadlines--such and such task must complete within a specified number of computer cycles, or before a certain clock time.
The processor resources must be spread among tasks in a way which is equitable and efficacious. For well-behaved tasks, the needed resources can be estimated and appropriate resources allocated. The operating system identifies tasks which must be completed to achieve forward progress in one or more programs which are active and schedules those tasks for execution in the processor, perhaps in the form of a task list. The processor takes each task and executes it. Some tasks can be completed in a single processor cycle, others take a small number of cycles, while still others require a considerable number of cycles. Typical examples of such might be, respectively: a simple read; get two numbers from memory, perform a mathematical operation, and restore the result to memory; or transform one line of video data quickly so that it can be output and transformation can begin on the next line. Tasks of arbitrarily large size can execute successfully under such a system.
However, in order for the computer system to be interactive it must accept asynchronous inputs. Such asynchronous events might include input from a computer keyboard ("the next character is an `a`"), mouse movement, insertion of a floppy disk, the ringing of a telephone, or the presence of a video frame for input. In general, such an asynchronous input needs to be recognized and dealt with within a certain amount of time. While any such input requires a diversion of system resources, when the frequency or size of such events gets large (a frame of video has orders of magnitude more information than a simple keyboard input), this can completely disrupt the earlier allocation of resources within resource constraints. Such a disruption can require a reallocation of processor resources to accommodate asynchronous events and to reschedule the original tasks.
When a single processor is available, the scheduling problem is well understood. Scheduling is commonly based on a rate monotonic scheduling policy. Other scheduling policies have been used, and still others studied academically, but rate monotonic is the most common.
If additional processors are made available, as in a multiprocessor system, scheduling becomes more complex. It turns out that for two processors the scheduling task becomes easier, but for more than two processors, optimized scheduling is very complex and is considered by many to be an intractable problem.
Referring to FIG. 1, the operating system 10 , which may be a real time operating system, includes process space 12 which enqueues a number of tasks 14 (1 to n tasks). System hardware 20 communicates with execution space through interrupts 18, RAM 16, and support hardware (not shown). Hardware devices such as disk drives, keyboards, input/output devices and the like are represented generically as hardware 20, which is in communication with operating system 10 through a plurality of interrupts 18 A typical interrupt may be a keypress on a keyboard. The interrupt event is noted in the process space, and an event is dispatched to ascertain the type of interrupt and to collect any associated data. To service the interrupt, execution cycles must be allocated or shared.
Interrupts often are of high priority. No matter the priority, when servicing an interrupt, it becomes necessary to recompute schedules for the initially scheduled tasks. It is important, therefore, that interrupts be serviced without major disruption of existing schedules.
In addition, it is desirable to minimize interrupt latencies. Such latencies arise primarily in the interrupt handler, typically special software or code designed to process the interrupt and respond as needed. Traditionally, programmers seek to minimize the code in an interrupt handler, then relegate recomputation of real time processes to the scheduler in the operating system kernel. In general, it is necessary to reprioritize to accommodate the interrupt.
To view the problem succinctly, processing resources must be divided between forward progress and scheduling. Forward progress includes successful execution of program tasks, such as user input and output to the user, computations on data to prepare for display, e.g. calculation of 3D polygons, and the like. Scheduling includes processing necessary to identify, prioritize and otherwise allocate tasks for forward progress. To accommodate interrupts, scheduling, and other tasks, some 31% of the processing power is reserved for overhead and is not available for forward progress. This overhead is used for scheduling and other support tasks. Unfortunately, most of the time much of this overhead is unused. Under rate monotonic scheduling policies, about 31% of the processing power is reserved for overhead. Reserving unneeded overhead significantly reduces the utilization of the processor.
The scheduling processing portion is itself divided into two primary components--the scheduling algorithm and context switching overhead, accounting for approximately 67 and 33%, respectively, of the scheduling processing resources.
What is needed is a real time operating system than can manage scheduling, deadline processing, and interact with asynchronous inputs without such a massive commitment to largely unused overhead. Preferably such an operating system would be readily scalable to multiprocessor systems.